COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	$$
C00008 ENDMK
C⊗;
$$;
David M. Perlman
University of California, San Diego
La Jolla, California 92037

Dear David:

$JI read with interest the paper you sent me.  Your algorithm
parallels very closely some parts of the algorithm published in the
paper which I am sending you.  I must say that the description in
the paper is not the clearest.  The problem attacked is slightly
more general: one wishes to find a system of distinct
representatives for a tuple of subsets of X, where G acts on X, and
each tuple is of the form (U↓1,U↓2,...,U↓k) where the U↓i's are
disjoint, and |U↓i|=n↓i. We call this "labelling" X such that n↓i of
the elements of X recieve label i.  In the special case where k=2,
this corresponds directly to finding an s.d.r. of n↓1-subsets of X.
However, the first result is that one can label with k types of
labels by labelling with the first type of label, and then labelling
the "unlabelled" elements of X with the remaining labels, using the
reduced symmetry group.  The next result is that if G is not
transitive (i.e., if there are orbits of G as it acts on X), then
one can do one orbit at a time.

Thus the problem reduces to something similar to the one in your
paper (it is also know that the group is transitive).  The third
result is very similar to yours;  one constructs a set which
contains an s.d.r. but might actually have equivalent items;
those are eliminated by checking each of the results if they
are "minimal" according to a lexicographical ordering.  The
"candidate" sets, however, are different;  I believe, now,
that there is a whole class of possible candidate sets one
could chose in order to find a s.d.r; for example, I chose,
at the time:

	To find an s.d.r. for k-subsets of X under the group G,
find an s.d.r. of (k-1)-subsets of X-{x↓1} under the stabilizer
subgroup of {x↓1}; the set of candidates is then the set of
those results, conjoined with {x↓1}.  In general, one could
choose to take an s.d.r. of i-subsets of X, and then for each U in that s.d.r.,
find an s.d.r. of (k-i)-subsets of (X-U) wrt the stabilizer of U.
In your case, you took i=k-1; in mine, I chose i=1 (since G is
transitive, {{x↓1}} is an s.d.r. of 1-subsets of X under G).
I am not sure, off hand, which i is optimal; you're solution
has merit.  It might be interesting to do some analysis of the
efficiency of these algorithms; any such constructive algorithm
must take at least as many number of steps as there are possible
solutions;  further, it seems difficult to find an algorithm
which would take less than |G|*|s.d.r.|.  I wonder how close
any of these methods might come to that bound.

As for your paper, I only have a few comments:
There is some confusion between "enumerating" and "counting", despite
Le Berge's clarification;  I would suggest emphasis that you have
a method for construction, and not just counting.
Also, I am not sure how appropriate the word "backtracking" is;  I have
a prejudice that "backtracking" applies to search procedures, rather
than generative procedures;  admitedly, generative procedures have
very little use outside of providing candidates for additional
heuristics in a search application.

But this is all just quibbling with wording.  I thank you for sending
me your paper and hope we can correspond in the future.


			Sincerely,




			Larry Masinter